package com.example.leetdemo.finash;

import java.util.*;

public class Solution652 {

    Map<String, TreeNode> treeMap = new HashMap<>();
    List<TreeNode> treeNodes = new ArrayList<>();
    Set<String> set = new HashSet<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return treeNodes;
        }
        findSeries(root);
        set.forEach(node -> {
            if (treeMap.get(node) != null) {
                treeNodes.add(treeMap.get(node));
            }
        });
        return treeNodes;
    }

    private String findSeries(TreeNode treeNode) {
        if (treeNode == null) {
            return "";
        }
        StringBuilder value = new StringBuilder();
        if (treeNode.left == null && treeNode.right == null) {
            value.append("#" + treeNode.val);
        } else {
            value.append("#M" + treeNode.val);
        }
        if (treeNode.left != null) {
            value.append("#L-");
            value.append(findSeries(treeNode.left));
            value.append(";");
        } else {
            value.append("#L;");
        }
        if (treeNode.right != null) {
            value.append("#R-");
            value.append(findSeries(treeNode.right));
            value.append(";");
        } else {
            value.append("#R;");
        }
        if (set.contains(value.toString())) {
            treeMap.put(value.toString(), treeNode);
        } else {
            set.add(value.toString());
        }
        return value.toString();
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
